1. Field of the Invention
The present invention relates to a method of creating parity information for error correction, and more particularly, to a method of converting a parity check matrix for low density parity check coding.
2. Description of the Related Art
A low density parity check (LDPC) coding method has been widely used for creating information for error correction. The LDPC coding method is used to obtain parity information by using a low density parity check matrix H containing only 0's and 1's in which the number of 1's is far smaller than the number of 0's. The LDPC code is regular if each row and each column of the parity check matrix H contains the same number of 1's, and irregular otherwise. The numbers of 1's included in each row and each column of the parity check matrix H is called the “row degree” and the “column degree,” respectively.
A method of creating parity information by using the LDPC coding method is usually accomplished based on the following equation:HX=0,  Equation 1where, H is an m×n parity check matrix;    X is a code word matrix including m message data and p parity data; and    m+p=n (where m, n, and p are integers).
The basic concept of the LDPC coding is disclosed in D. J. MacKay, “Good Error-correction Codes Based on Very Sparse Matrices,” IEEE Trans. on Information Theory, Vol. 45, No. 2, pp. 399-431. According to this disclosure, the parity information can be created by solving the above Equation 1 by using matrix manipulation using a Gaussian elimination method. However, such matrix manipulation requires a large number of calculations.
Recently, a more convenient method of solving the above Equation 1 has been introduced. According to this method, the parity check matrix H is converted into a rearranged parity check matrix H′ which includes a specific type of sub-block, called a lower triangular matrix. The converted parity check matrix H′ is used to create the parity information in a sequential manner. This method is disclosed in T. Richardson, R. Urbanke, “Efficient Encoding of Low Density Parity Check Codes,” IEEE Trans. on Information Theory, Vol. 47, No. 2, pp. 638-656, 2001.
A conventional method of converting a parity check matrix H will now be described with reference to FIG. 1 and FIGS. 2A through 2F.
FIG. 1 is a flow chart illustrating a conventional method of converting the parity check matrix H into the rearranged parity check matrix H′, and FIGS. 2A through 2F illustrate matrices resulting from each operation shown in FIG. 1. This conventional method is called the “greedy algorithm.”
In operation 110, all the columns linked with a first row in the matrix H are made the leftmost columns of the matrix H. Herein, “a column linked with a specific row” is a column having 1's in the specific row, and the linked columns can be moved by i) exchanging or ii) shifting rows or columns. FIG. 2A shows a matrix after performing operation 110, in which the first row includes four 1's.
In operation 120, a current search area is defined as a matrix A1 in FIG. 2B not including the first row and the columns linked with the first row in the matrix H. The search area A1 functions as a reference area for determining the number of 1's in a row search or a column search which is accomplished in the following manner.
In operation 130, rows R1, R2, . . . , Rk having row degrees of one are found in the matrix A1. In FIG. 2C, the reference numerals, R1, R2, . . . , Rk, represent the rows having one “1” (i.e., a row degree of one) in the search area A1.
In operation 140, it is determined whether a row having a degree of one has been found as a result of the search. If a row having a degree of one is found, operations 150, 160, 170 and 180 are carried out.
In operation 150, the rows R1, R2, . . . , Rk and the columns C1, C2 . . . , Cm, linked with the rows R1, R2, . . . , Rk are sequentially moved to the upper left side of the matrix A1 through row movement and column movement, respectively. For example, if rows R1 and R2 have degrees of one, the column C1 linked with the row R1 is made the leftmost column of the matrix A1, and the row R1 is made the uppermost row of the matrix A1. Then, the column C2 linked with the row R2 is made the second leftmost column in the matrix A1, and the row R2 is made the second uppermost row in the matrix A1. As a result, a unit matrix I1 is created in the upper left side of the matrix A1 as shown in FIG. 2D.
In operation 160, a current index, i, representing an index of a first column in the current search area is incremented by the number of rows, k, found in operation 130. For example, in FIG. 2D, the current index, i, is 5, and the number of rows, k, is 2.
In operation 170, the current search area is updated to be a matrix A2 not including the unit matrix I1 in the search area A1 as shown in FIG. 2E.
In operation 180, it is determined whether the current index i is larger than the number of rows, n, of the parity check matrix H. If the current index i is smaller than the number of rows, n, then operation 130 is performed again. Otherwise, the matrix conversion procedure is terminated.
If a row having a degree of one is not found in operation 140, operations 155, 165, 175 and 185 are carried out.
In operation 155, a row Rmin having a lowest degree is searched for in the matrix A1.
In operation 165, columns Cmin1, Cmin2, . . . , CminI (I is an integer) linked with the row Rmin are found, and all but one of the columns Cmin1, Cmin2 . . . , CminI are made the leftmost columns of the matrix H as shown in FIG. 2F.
In operation 175, the current index, i, representing an index of a first column in the current search area is incremented by I−1. For example, in FIG. 2F, the current index, i, is 5, and the number of rows, k, is 3.
In operation 185, the search area is updated to be a matrix A2 excluding the columns moved in operation 165, as shown in FIG. 2G.
In operation 195, it is determined whether the current index, i, is larger than the number of rows, n, of the parity check matrix H. If the current index, i, is smaller than the number of rows, n, then operation 130 is performed again. Otherwise, the matrix conversion procedure is terminated.
FIG. 2H illustrates a converted matrix H′ produced according to the conventional method. The converted matrix H′ shown in FIG. 2H includes an identity matrix composed of unit matrices chained in a diagonal direction. A parity information calculation is carried out by using the right upper block D, which is the block filled only with 0's.
As a necessary condition for sequentially calculating the parity information, the converted matrix H′ should contain a submatrix having a diagonal line of 1's, and the submatrix should be a lower triangular matrix. The converted matrix H′ in FIG. 2H satisfies this condition.
The load for calculating parity information in the matrix H decreases as the size of the submatrix I increases. In other words, according to the conventional method, as the size of the submatrix increases, the calculation load for creating parity information decreases.
However, since the submatrix I of FIG. 2H must be an identity matrix, the size of the submatrix I can only increase to a limited degree. In other words, according to the conventional art, since the submatrix for sequential parity calculation is an identity matrix, the size of the submatrix I can only be increased to a limited amount. The more limited the size of matrix 1, the amount of calculation for decoding using the parity check matrix H increases. However, it is desired that the submatrix I of the converted matrix H′ be a lower triangular matrix instead of an identity matrix, such that the size of the submatrix I can be larger than that shown in FIG. 2H.